#include <stdio.h>
#include <stdlib.h>

// 定义链表节点结构体
typedef struct ListNode {
    int val;
    struct ListNode* next;
} ListNode;

// 创建链表节点
ListNode* createNode(int val) {
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
    newNode->val = val;
    newNode->next = NULL;
    return newNode;
}

// 创建链表
ListNode* createList() {
    int num;
    ListNode* dummy = createNode(0); // 创建虚拟头节点
    ListNode* current = dummy;

    while (scanf("%d", &num) && num != -1) {
        current->next = createNode(num);
        current = current->next;
    }
    return dummy->next; // 返回链表头节点
}

// 合并两个非降序链表
ListNode* mergeLists(ListNode* S1, ListNode* S2) {
    ListNode* dummy = createNode(0); // 创建虚拟头节点
    ListNode* current = dummy;

    while (S1 && S2) {
        if (S1->val <= S2->val) {
            current->next = S1;
            S1 = S1->next;
        } else {
            current->next = S2;
            S2 = S2->next;
        }
        current = current->next;
    }

    // 如果其中一个链表还有剩余，直接接在后面
    if (S1) {
        current->next = S1;
    } else if (S2) {
        current->next = S2;
    }

    return dummy->next; // 返回合并后的链表头节点
}

// 打印链表
void printList(ListNode* head) {
    if (!head) {
        printf("NULL\n");
        return;
    }
    while (head) {
        printf("%d", head->val);
        head = head->next;
        if (head) {
            printf(" ");
        }
    }
    printf("\n");
}

// 释放链表内存
void freeList(ListNode* head) {
    while (head) {
        ListNode* temp = head;
        head = head->next;
        free(temp);
    }
}

int main() {
    // 创建两个链表
    printf("请输入第一个非降序链表序列（以-1结尾）：\n");
    ListNode* S1 = createList();
    printf("请输入第二个非降序链表序列（以-1结尾）：\n");
    ListNode* S2 = createList();

    // 合并链表
    ListNode* S3 = mergeLists(S1, S2);

    // 输出合并后的链表
    printf("合并后的非降序链表为：\n");
    printList(S3);

    // 释放链表内存
    freeList(S1);
    freeList(S2);
    freeList(S3);

    return 0;
}